package com.lwt.codetop.linkedLists;
//21. 合并两个有序链表

/**
 * 思路：归并排序中的归并操作，将两个有序链表进行归并
 */
public class MergeTwoSortedLists {
    public static void main(String[] args) {
        // 1. 构建测试用例
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(4);

        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);

        // 2. 合并两个有序链表
        ListNode p = mergeTwoLists(list1, list2);
        while(p != null){
            System.out.print(p.val + " ");
            p = p.next;
        }
    }

    /**
     * 归并排序的归并过程，归并两个有序链表(合并 + 扫尾)
     * @param list1
     * @param list2
     * @return
     */
    private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        // 1. 归并
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        // 2. 扫尾
        if(list1 != null) cur.next = list1;
        if(list2 != null) cur.next = list2;
        return dummy.next;
    }
}
